package com.computer.fundamentals.datastructure;

public class SampleHashMap {

    public static final int DEFAULT_INITIAL_LENGTH = 4; // 默认初始大小

    public ListNode[] bucket; // 哈希桶

    public double threshOld; // 阈值

    public int size; // 现有存量

    public int capacity; // 容量

    static class ListNode {
        int key;
        int val;
        ListNode next;
        public ListNode(int key_, int val_) {
            this.key = key_;
            this.val = val_;
        }
    }
    /**
     * 构造器
     */
    public SampleHashMap() {
        this.capacity = DEFAULT_INITIAL_LENGTH;
        this.bucket = new ListNode[capacity];
        this.size = 0;
        this.threshOld = 0.75;
    }

    /**
     * 插入元素
     */
    public void put(Integer key, Integer value) {
        int idx = hash(key) & (capacity - 1);
        ListNode newNode = new ListNode(key, value);
        if (bucket[idx] == null) {
            bucket[idx] = newNode;
            size++;
        }else {
            ListNode cur = bucket[idx];
            boolean flag = false;
            while (cur != null) {
                if (cur.key == key) {
                    cur.val = value;
                    flag = true;
                    break;
                }
                cur = cur.next;
            }
            if (!flag) {
                newNode.next = bucket[idx];
                bucket[idx] = newNode;
            }
        }
        if ((double) size / (double) capacity >= 0.75) {
            resize();
        }
    }

    /**
     * 获取元素
     */
    public Integer get(Integer key) {
        int idx = hash(key) & (capacity - 1);
        ListNode cur = bucket[idx];
        if (cur != null) {
            while (cur != null) {
                if (cur.key == key) {
                    return cur.val;
                }
                cur = cur.next;
            }
        }
        return null;
    }

    /**
     * 判断哈希表是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 扩容
     */
    public void resize() {
        if (capacity * 2 >= 1024) {
            return;
        }
        int newCapacity = capacity * 2;
        ListNode[] newBucket = new ListNode[newCapacity];
        int newSize = 0;
        for (int i = 0;i < capacity;i++) {
            if (bucket[i] != null) {
                ListNode cur = bucket[i];
                while (cur != null) {
                    int newIdx = hash(cur.key) & (newCapacity - 1);
                    if (newBucket[newIdx] == null) {
                        newSize++;
                    }
                    ListNode oldNode = newBucket[newIdx];
                    ListNode newNode = new ListNode(cur.key, cur.val);
                    newNode.next = oldNode;
                    newBucket[newIdx] = newNode;
                    cur = cur.next;
                }
            }
        }
        bucket = newBucket;
        capacity = newCapacity;
        size = newSize;
    }

    /**
     * 哈希函数
     */
    private int hash(Integer key) {
        int h;
        return (key != null) ? (h = key.hashCode()) ^ (h >>> 16): 0;
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        SampleHashMap sampleHashMap = new SampleHashMap();
        System.out.println(sampleHashMap.isEmpty());
        for (int i = 0;i < 100;i++) {
            sampleHashMap.put(i, i + 10);
        }
        for (int i = 0;i < 100;i++) {
            System.out.println(sampleHashMap.get(i));
        }
    }
}